class Solution(object):
    def countPartitions(self, nums, k):
        total = 0
        base = 10 ** 9 + 7
        dp = [0] * (k + 1)
        dp[0] = 1
        for num in nums:
            next_dp = [0] * (k + 1)
            for last_num in range(min(k + 1, total + 1)):
                other_num = total - last_num
                min_val = min(min(last_num + num, other_num), k)
                next_dp[min_val] += dp[last_num]
                next_dp[min_val] %= base
                min_val = min(min(last_num, other_num + num), k)
                next_dp[min_val] += dp[last_num]
                next_dp[min_val] %= base
            total += num
            dp = next_dp
        return dp[-1]


data = Solution()
nums = [1, 2, 3, 4]
k = 4
nums = [6, 6]
k = 2
print(data.countPartitions(nums, k))
